package com.codingvip.dynamic;

/**
 * @author hansongtao
 */
public class Package {
    private int maxW = Integer.MAX_VALUE;
    private static int[] weight ={2,2,4,6,3};
    private static int[] value = {3, 4, 8, 9, 6};
    private int n = 5;
    private int maxWeightOfPackage = 9;

    public static void main(String[] args) {
        Package pa =new Package();
//        pa.f(0, 0);
//        int result = pa.knapsack(weight, 5, 9);
//        int result = pa.knapsackVersion2(weight, 5, 9);
        //考虑价值
        int result = pa.knapsackVersion3(weight,value, 5, 9);
        System.out.println(result);

    }

    private int knapsackVersion3(int[] weight, int[] value, int n, int w) {
        int[][] states = new int[n][w + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < w + 1; j++) {
                states[i][j] = -1;
            }
        }
        states[0][0] = 0;
        if (weight[0] <= w) {
            states[0][weight[0]] = value[0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; ++j) {
                //当 第i 个物品没有入背包时
                if (states[i-1][j] >0) {
                    states[i][j] = states[i - 1][j];
                }
            }
            for (int j = 0; j <= w - weight[i]; ++j) {
                if (states[i - 1][j] >=0) {
                    int v = states[i - 1][j] + value[i];
//                    if(v>)
                }
            }
        }
        showResultVersion3(n, w, states);
        for (int i = w; i >=0; --i) {
            if (states[n - 1][i] >=0) {
                return i;
            }
        }
        return 0;
    }

    private void showResultVersion3(int n, int w, int[][] states) {


    }

    /**
     *
     * @param i
     * @param cw
     */
    public void f(int i, int cw) {
        if (cw == maxWeightOfPackage || i == n) {
            if (cw > maxW) {
                maxW = cw;
            }
            System.out.println("======" + cw);
            return;
        }
        f(i + 1, cw);
        if (cw + weight[i] <= maxWeightOfPackage) {
//            packageRecord[i] = 1;
            f(i + 1, cw + weight[i]);
        }
    }

    /**
     *
     * @param weight 物品重量
     * @param n  物品个数
     * @param w  背包可承载的重量
     * @return
     */
    public int knapsack(int[] weight, int n, int w) {
        boolean[][] states = new boolean[n][w + 1];
        states[0][0]=true;
        if (weight[0] <= w) {
            states[0][weight[0]] = true;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; ++j) {
                //当 第i 个物品没有入背包时
                if (states[i-1][j] == true) {
                    states[i][j] = states[i - 1][j];
                }
            }
            for (int j = 0; j <= w - weight[i]; ++j) {
                if (states[i - 1][j] == true) {
                    states[i][j+weight[i]]=true;
                }
            }
        }
        showResult(n, w, states);
        for (int i = w; i >=0; --i) {
            if (states[n - 1][i] == true) {
                return i;
            }
        }
        return 0;
    }


    /**
     *  使用一维数据
     * @param weight 物品重量
     * @param n  物品个数
     * @param w  背包可承载的重量
     * @return
     */
    public int knapsackVersion2(int[] weight, int n, int w) {
        boolean[] states = new boolean[w + 1];
        states[0]=true;
        if (weight[0] <= w) {
            states[weight[0]] = true;
            System.out.println("设置states【" + weight[0] + "】=true");
        }
        for (int i = 1; i < n; i++) {
            for (int j = w - weight[i]; j>=0;--j) {
                if (states[j] == true) {
                    states[j+weight[i]]=true;
                    System.out.println("设置states【" +(j+weight[i]) + "】=true,j="+j+",i=="+i);
                }
            }
        }
//        showResult(n, w, states);
        showResultVersion2(w, states);
        for (int i = w; i >=0; --i) {
            if (states[i] == true) {
                return i;
            }
        }
        return 0;
    }
    private void showResultVersion2(int w, boolean[] states) {
            for (int j = 0; j <=w; j++) {
                if (states[j] == true) {
                    System.out.print("1 ");
                }else{
                    System.out.print("0 ");
                }
            }
            System.out.println("");

    }
    private void showResult(int n, int w, boolean[][] states) {
        System.out.println("--:- 0 1 2 3 4 5 6 7 8 9 ");
        for (int i = 0; i < n; i++) {
            System.out.print("W" + i + ":" + weight[i]+" ");
            for (int j = 0; j <=w; j++) {
                if (states[i][j] == true) {
                    System.out.print("1 ");
                }else{
                    System.out.print("0 ");
                }
            }
            System.out.println("");

        }
        System.out.println("");
    }

    private void showResultValue(int n, int w, int[][] states) {
        System.out.println("--:- 0 1 2 3 4 5 6 7 8 9 ");
        for (int i = 0; i < n; i++) {
            System.out.print("W" + i + ":" + weight[i]+" ");
            for (int j = 0; j <=w; j++) {
                if (states[i][j] >=0) {
                    System.out.print(states[i][j]+" ");
                }else{
                    System.out.print("-1 ");
                }
            }
            System.out.println("");

        }
        System.out.println("");
    }

}
